package sliding_window

/*
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空

Example1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

*/

// 此方式时间复杂度为O(m+n)
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	m, n := len(nums1), len(nums2)
	r := make([]int, 0, m+n)
	i, j := 0, 0
	for i < m && j < n {
		v1 := nums1[i]
		v2 := nums2[j]

		if v1 < v2 {
			r = append(r, v1)
			i++
		} else {
			r = append(r, v2)
			j++
		}
	}

	if i < m {
		r = append(r, nums1[i:]...)
	}

	if j < n {
		r = append(r, nums2[j:]...)
	}

	count := m + n
	if count&1 == 1 {
		k := (count - 1) / 2
		return float64(r[k])
	} else {
		k := count / 2
		return (float64(r[k-1]) + float64(r[k])) / 2
	}
}

//此方式时间复杂度为 O(log(m + n))
/*

	nums1																	nums2
	midA-1|midA																midB-1|midB
				max(nums1[midA-1],nums2[midB-1])		 min(nums1[midA],nums2[midB]])
                                                   mid


*/
func findMedianSortedArrays2(nums1 []int, nums2 []int) float64 {
	if len(nums1) > len(nums2) {
		return findMedianSortedArrays2(nums2, nums1)
	}

	//主要是为了查找nums1Mid和nums22Mid的位置
	low, high, k, nums1Mid, nums2Mid := 0, len(nums1), (len(nums1)+len(nums2)+1)>>1, 0, 0
	for low <= high {
		//分界线 mid-1 | mid
		nums1Mid = low + (high-low)>>1
		nums2Mid = k - nums1Mid
		//调整双指针
		if nums1Mid > 0 && nums1[nums1Mid-1] > nums2[nums2Mid] {
			high = nums1Mid - 1
		} else if nums1Mid != len(nums1) && nums1[nums1Mid] < nums2[nums2Mid-1] {
			low = nums1Mid + 1
		} else {
			break
		}
	}

	midLeft, midRight := 0, 0
	if nums1Mid == 0 {
		midLeft = nums2[nums2Mid-1]
	} else if nums2Mid == 0 {
		midLeft = nums1[nums1Mid-1]
	} else {
		midLeft = max(nums1[nums1Mid-1], nums2[nums2Mid-1])
	}
	if (len(nums1)+len(nums2))&1 == 1 {
		return float64(midLeft)
	}

	if nums1Mid == len(nums1) {
		midRight = nums2[nums2Mid]
	} else if nums2Mid == len(nums2) {
		midRight = nums1[nums1Mid]
	} else {
		midRight = min(nums1[nums1Mid], nums2[nums2Mid])
	}

	return float64(midLeft+midRight) / 2
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}
